#include<stdio.h>
#include<stdlib.h>
struct node{
int num;
struct node *next;
};


struct node *first=NULL;

struct node *top=NULL;
int count,c;

// For creating linked list

struct node *add_list(struct node *list , int n)
{
struct node *new_node;
new_node=malloc(sizeof(struct node));
if(new_node==NULL)
{
printf("memory not allocated");
 }
new_node->num=n;
new_node->next=list;
return new_node;
}


void *read(void)
{
int n;int i;
printf("Enter  number of nodes");
scanf("%d",&count);
for(i=0;i<count;i++)
{scanf("%d",&n);
first = add_list(first,n);}
}

// Remove function

struct node *rem(struct node *list, int n)
{
  struct node *cur, *prev;
      
  for (cur = list, prev = NULL;
      cur!=NULL&&cur->num != n;
       prev = cur, cur = cur->next)
    ;
  if (cur == NULL) 
    return list;            
  
   if (prev == NULL)
    list = list->next;    
  else
    prev->next = cur->next;  
  free(cur);
  count=count-1;
  return list;

  
}

// Insert function

struct node *insert(struct node *list, int k,int m)
{
int i;
struct node *cur, *prev, *new_node;
 new_node = malloc(sizeof(struct node));
  if (new_node == NULL) {
    printf("Database is full; can't add more parts.\n");
    return;
}
new_node->num=m;
for (cur = list, prev = NULL,i=0;
       cur != NULL && i!=k;
       prev = cur, cur = cur->next,i++)
     ;
  new_node->next = cur;
  if (prev == NULL)
    list = new_node;
  if (prev == NULL)
    list = list->next;      
  else
    prev->next = new_node;
 count=count+1;
 return list;

}

// Pop function

struct node *pop(struct node *list, int k)
{
  struct node *cur, *prev;
  int i;	  
  for (cur = list, prev = NULL,i=0;
       cur != NULL && i!=k;
       prev = cur, cur = cur->next,i++)
    ;
  if (cur == NULL) 
    return list;            
  if (prev == NULL)
    list = list->next;       
  else
    prev->next = cur->next;  
  free(cur);
  count=count-1;
  return list;

  
} 

//Append function

struct node *append(struct node*list,int m)
{
struct node *cur, *prev, *new_node;
 new_node = malloc(sizeof(struct node));
  if (new_node == NULL) {
    printf("Database is full; can't add more parts.\n");
    return;}
  new_node->num=m;
for (cur = list, prev = NULL;
       cur != NULL ;
       prev = cur, cur = cur->next)
;
prev->next=new_node;
new_node->next=NULL;
count=count+1;
return list;
}

//Reverse function

struct node* reverse(struct node*list)
{ int n;
   

   struct node* temp,* temp1,* temp2;
    temp=malloc(sizeof(struct node));
    temp1=malloc(sizeof(struct node));
    temp2=malloc(sizeof(struct node));
    temp=list;temp1=temp->next;temp2=temp1->next;
    temp->next->next=NULL;
    while(temp2!=NULL)
    {
        temp=temp1;
        temp1=temp2;
        temp2=temp1->next;
        temp1->next=temp;
    }
    
  first=append(temp1,list->num);   
return first;
}


//Index function

void *ind(struct node*list,int m)
{
int i,flag=0;
 struct node *p=list;
for(p=list,i=0;p!=NULL&&i<count;p=p->next,i++)
{ if(p->num==m)
 { flag=1;
break;}}
if(flag)
printf("Index of %d ==%d\n",m,i);
else
printf("No such element exits"); 
   
}

//Count function

void *Count(struct node*list,int m)
{
int i,s=0;
 struct node *p;

for(p=list,i=0;p!=NULL,i<count;p=p->next,i++)
{ if(p->num==m)
  s=s+1;
}
printf("Number of %d occurs == %d\n",m,s);
}



struct node *add_list2(struct node *list , int n)
{struct node *new_node2;
new_node2=malloc(sizeof(struct node));
if(new_node2==NULL)
{
printf("memory not allocated");
 }
new_node2->num=n;
new_node2->next=list;
return new_node2;
}

void *read3()
{
int n;int i;
printf("Enter number of nodes of new list to be added");
scanf("%d",&c);
for(i=0;i<c;i++)
{scanf("%d",&n);
top = add_list2(top,n);}
}

//Extend function

struct node *extend(struct node*list)
{
struct node *cur, *prev, *new_node;
read3();
for (cur = list, prev = NULL;
       cur != NULL ;
       prev = cur, cur = cur->next)
;
prev->next=top;
top=NULL;

count=count+c;
return list;
}

//Print function

struct node *print(struct node * list)
{
struct node *p;
for(p=list;p!=NULL;p=p->next)
printf("%d-->",p->num);
}

//Sort function(Bubble sort)

struct node *sort(struct node *list)
                               
{
int i, j, tmp ;
struct  node *temp1, *temp2 ;
temp1=list;
temp2=list->next;
for(i=0;i<count;i++)
{
temp1=list;
temp2=temp1->next;
for ( j = 1 ;j<count-i ; j++ )
{
if (( temp1->num) > (temp2->num) )
{
tmp = temp1->num;
temp1->num = temp2->num ;
temp2->num = tmp ;
}
temp1 = temp1->next ;
temp2 = temp2->next ;
}
  
}  

return list;
}




int function(struct node *p,int ch)
{int c=1;
struct node *l;
int D;
switch(ch)
{
case 1:while(c)
           {int m,k;
            printf("Enter the element to insert and the index");
            scanf("%d,%d",&m,&k);
            l=insert(p,k,m);
            print(l);
            printf("Press 1 to enter more elements ,0 to exit");
            scanf("%d",&c);
            }
            break;

case 2 : while(c)
           {int m,k;
            printf("Enter the element to append");
            scanf("%d",&m);
            l=append(p,m);
            print(l);
            printf("Press 1 to append more elements ,0 to exit");
            scanf("%d",&c);
            }
            break;

case 3:  first= reverse(p);
         print(first);
         break;
case 4 :while(c)
           {int m,k;
            printf("Enter the index");
             scanf("%d",&k);
             l=pop(p,k);
             print(l);
             printf("Press 1 to pop more elements ,0 to exit");
             scanf("%d",&c);
            }
            break;

case 5 :  l=sort(p);
          print(l);
          break;
case 6 :while(c)
           {int m,k;
            printf("Enter the element to delete");
            scanf("%d",&m);
            l=rem(p,m);
            print(l);
            printf("Press 1 to delete more elements ,0 to exit");
            scanf("%d",&c); 
            }
           break;
case 7 : while(c)
           {
            l=extend(p);
            print(l);
            printf("Press 1 to extend more elements ,0 to exit");
            scanf("%d",&c);
            }

           break; 
case 8: while(c)
           {int m,k;
            printf("Enter the element to count");
            scanf("%d",&m);
            Count(p,m);
            printf("Press 1 to count more elements ,0 to exit");
            scanf("%d",&c);
            }
             break; 
case 9: while(c)
           {int m,k;
            printf("Enter the element to find index");
            scanf("%d",&m);
            ind(p,m);
            printf("Press 1 to find index of more elements ,0 to exit");
            scanf("%d",&c);
            }

            
}
printf("Want to enter more functions Press 1 , 0 to exit");
scanf("%d",&D);
if(D)
return 1;
else
return 0;
}





int main()
{
int z,t,C=1;
read();
while(C)
{printf("\n FUNCTIONS:");

                printf("\n 1.Insert");

                printf("\n 2.Append");

                printf("\n 3.Reverse");

                printf("\n 4.Pop ");

                printf("\n 5.Sort");

                printf("\n 6.Remove");

                printf("\n 7.Extend");

                printf("\n 8.Count");

                printf("\n 9.Index");

                
printf("\nEnter function");
scanf("%d",&t);
z=function(first,t);
if(z)
C=1;
else C=0;
}
}